<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Common Pitfalls
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial020.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial012.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial022.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc47">3.9</A>&nbsp;&nbsp;Common Pitfalls</H2><UL>
<LI><A HREF="tutorial021.html#toc28">Unification works both ways</A>
<LI><A HREF="tutorial021.html#toc29">Unexpected backtracking</A>
</UL>

Prolog is different from conventional programming languages, and a common
problem is to program Prolog like a conventional language. Here are some
points to note:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Unification is more powerful than normal case discrimination (see 
 section&nbsp;<A HREF="#unif">3.9.1</A>); 
<LI CLASS="li-itemize">Prolog procedure calls are more powerful than conventional procedure
calls. In particular, backtracking is possible (see section&nbsp;<A HREF="#back">3.9.2</A>);
</UL>
<A NAME="toc28"></A>
<H3 CLASS="subsection"><A NAME="htoc48">3.9.1</A>&nbsp;&nbsp;Unification works both ways</H3>
<A NAME="unif"></A>
One common problem is to write a predicate expecting certain instantiation
patterns for the arguments, and then get unexpected results when the 
arguments do not conform to the expected pattern. An example is the
member relation, intended to check if an item <CODE>Item</CODE> is a member of
a list or not. This might be written as:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
member(Item, [Item|_]).
member(Item, [_|List]) :- member(Item, List).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The expected usage assumes both <CODE>Item</CODE> and the list are ground. In 
such cases, the above predicate does indeed check if <CODE>Item</CODE> occurs in
the list given as a second argument. However, if either of the arguments are
not ground, then potentially unexpected behaviour might occur. Consider
the case where <CODE>Item</CODE> is a variable, then the above predicate will 
enumerate the elements of the list successively through backtracking. On
the other hand, if any of the list elements of the list is a variable, they
would be unified with <CODE>Item</CODE>. Other instantiation patterns for either
arguments can produce even more complex results. <BR>
<BR>
If the intended meaning is simply to check if <CODE>Item</CODE> is a member of 
a list, this can be done by:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
  % is_member(+Element, +List)
  % check if Element is an element that occurs in a List of
  % ground elements
is_member(Item, [Element|_]) :- Item == Element.
is_member(Item, [_|List]) :- nonvar(List), is_member(Item, List).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Note the use of comments to make clear the intention of the use of the
predicate. The convention used is that `+' indicates that an argument should
be instantiated (i.e. not a variable), `-' for an argument that should be
an uninstantiated variable, and '?' indicates that there is no restrictions
on the mode of the argument.<BR>
<BR>
<A NAME="toc29"></A>
<H3 CLASS="subsection"><A NAME="htoc49">3.9.2</A>&nbsp;&nbsp;Unexpected backtracking</H3>
<A NAME="back"></A>
Remember that when coding in Prolog, any predicate <I>may</I> be backtracked 
into. So correctness in Prolog requires:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Predicate returns the correct answer when first called.
<LI CLASS="li-itemize">Predicate behaves correctly when backtracked into.
</UL>
Recall that backtracking causes alternative choices to be explored, if
there are any. Typically another choice corresponds to another clause
in the poredicate definition, but alternative choices may come from
disjunction (see above) or built-in predicates with multiple
(alternative) solutions. 
The programmer should make sure that a predicate will only produce
those solutions that are wanted. Excess alternatives can be removed by
coding the program not to produce them, or by the cut, or the conditional.<BR>
<BR>
For example, to return only the <I>first</I> member, in the
<CODE>is_member/2</CODE> example, 
the predicate can be coded using the cut, as follows:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
is_member(Item, [Element|_]) :- Item == Element, !.
is_member(Item, [_|List]) :- nonvar(List), is_member(Item, List).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

<H4 CLASS="subsubsection">Using conditional</H4>
Another way to remove excess choice points is the conditional:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
is_member(Item, [Element|List]) :- 
    ( Item == Element -&gt;
        true 
    ;
        nonvar(List), is_member(Item, List)
    ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<HR>
<A HREF="tutorial020.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial012.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial022.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
